import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[] arr = { 12, 3 , 8 , 11 , 9 , 5 , 20 , 18};
           quickSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i] ;
            int j = i-1 ;
            for( ; j >= 0 ; j--){
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    //arr[j+1] = tmp ;
                    break ;
                }
            }
                arr[j+1] = tmp ;
        }
    }
    public static void shellSort(int[] arr){
        int gap = arr.length ;
        while(gap > 1){
             gap = gap / 2 ;
             shell(arr , gap);
        }
    }
    private static void shell(int[] arr , int gap){
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i] ;
            int j = i-gap ;
            for( ; j >= 0 ; j-=gap){
                if(arr[j] > tmp){
                    arr[j+gap] = arr[j];
                }else{
                    break ;
                }
            }
            arr[j+gap] = tmp ;
        }
    }
     public static void selectSort(int[] arr){

        for (int i = 0; i < arr.length; i++) {
            int minIndex = i ;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]){
                    minIndex = j ;
                }
            }
            swap(arr , i , minIndex);
         }

     }
     private static void swap(int[] arr , int i , int minIndex){
         int tmp = arr[minIndex] ;
         arr[minIndex] = arr[i];
         arr[i] = tmp ;
     }

    public static void selectSort2(int[] arr){
        int left = 0 ;
        int right = arr.length -1 ;
        while(left < right){
            int maxIndex = left ;
            int minIndex = left;
            for (int i = left+1; i <= right; i++) {
                if(arr[i] < arr[minIndex]){
                    minIndex = i ;
                }
                if(arr[i] > arr[maxIndex]){
                    maxIndex = i ;
                }
            }
        swap(arr , minIndex , left);
            if(maxIndex == left){
                maxIndex = minIndex ;
            }
        swap(arr , maxIndex , right);
        left++ ;
        right-- ;
        }


    }
    public static void heapSort(int[] arr){
        createBigHeap(arr);
        int len = arr.length-1;
        while(len > 0){
            swap(arr , 0 , len);
            shiftDown(arr , 0 , len);
            len -- ;
        }

    }
    private static void createBigHeap(int[] arr){
        for (int parent = (arr.length-1-1)/2 ; parent >=0 ; parent--) {
            shiftDown( arr ,parent , arr.length);
        }
    }
    private static void shiftDown(int[] arr , int parent , int len){
        int child = parent*2 + 1 ;
        while(child < len){
            if(child+1 < len && arr[child+1] > arr[child]){
                child ++ ;
            }
            if(arr[child] > arr[parent]){
                swap(arr , parent , child);
                parent = child ;
                child = parent*2 +1 ;
            }else{
                break ;
            }
        }
    }
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean flg = false ;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr , j , j+1);
                    flg = true ;
                }
            }
            if(flg == false){
                return;
            }
        }

    }
    public static void quickSort(int[] arr){
        quick(arr , 0 , arr.length-1);
    }
    private static void quick(int[] arr , int start , int end){
        if(start >= end) return ;
        int pivot = partition(arr , start , end);
        quick(arr , start , pivot-1);
        quick(arr , pivot+1 , end);
    }
    private static int partition(int[] arr ,int left , int right){
        int key = arr[left];
        int tmp = left ;
        while(right > left){
            while(left < right && key <= arr[right]){
                right -- ;
            }
            while(left < right && key >= arr[left]){
                left++ ;
            }
            swap(arr , left , right);
        }
        swap(arr , tmp , left);
        return left ;
    }


}
